package org.example.SolutionNew002;

import java.util.PriorityQueue;

public class LinkedList13 {
    public static void main(String[] args) {
        LinkedList13 obj=new LinkedList13();
        ListNode h1=new ListNode(1);
        h1.next=new ListNode(4);
        h1.next.next=new ListNode(5);
        ListNode h2=new ListNode(1);
        h2.next=new ListNode(3);
        h2.next.next=new ListNode(4);
        ListNode[] temp=new ListNode[2];
        temp[0]=h1;temp[1]=h2;
        ListNode res=obj.mergeKLists(temp);
        while(res!=null){
            System.out.println(res.val);
            res=res.next;
        }

    }

    public ListNode mergeKLists1(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end)  return lists[start];
        if (start>end) return null;

        int mid=start+(end-start)/2;
        return mergeTwoList(merge(lists,start,mid),merge(lists,mid+1,end));
    }

    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while(l1!=null && l2!=null){
            if(l1.val<=l2.val){
                curr.next=l1;
                l1=l1.next;
            }else{
                curr.next=l2;
                l2=l2.next;
            }
            curr=curr.next;
        }
        ListNode temp= l1==null?l2:l1;
        curr.next=temp;
        return dummy.next;
    }

    PriorityQueue<Status> queue=new PriorityQueue<>();

    public ListNode mergeKLists(ListNode[] lists) {
        for(int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                queue.add(new Status(lists[i].val,lists[i]));
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while(!queue.isEmpty()){
            ListNode next=queue.poll().node;
            curr.next=next;
            curr=curr.next;
            if(next.next!=null){
                queue.add(new Status(next.next.val,next.next));
            }
        }
        return dummy.next;
    }
}

class Status implements Comparable<Status>{
    int val;
    ListNode node;

    public Status(int val, ListNode node) {
        this.val = val;
        this.node = node;
    }

    @Override
    public int compareTo(Status o) {
        return this.val - o.val;
    }
}
